package traverser;
/*	Queue.java
 * Implementation of a queue for the SIGART project
 * 
 * Author: Dan Roberts
 * Date: 9/18/11
 */
public class Queue<T> {
	
	private LLNode tail;   // For pushing
	protected LLNode head;   // For popping
	private int count;
	
	// Default Constructor
	public Queue () {
		tail = null;
		head = null;
		count = 0;
	}
	
	public int size () {
		return count;
	}
	
	// Add a value to the tail of the queue
	public void push (T value) {
		LLNode temp = new LLNode(value, tail);
		if (tail != null) {
			tail.prev = temp;
		}
		tail = temp;
		if (head == null) {
			head = tail;
		}
		count++;
	}
	
	// Take a value from the head of the queue
	public T pop () {
		if (head == null) {
			return null;
		}
		LLNode temp = head;
		head = head.prev;
		if (head != null) {
			head.next = null;
		}
		count--;
		return temp.value;
	}
	
	public boolean contains (T item) {
		LLNode iter = head;
		while (iter != null) {
			if (iter.value.equals(item)) {
				return true;
			}
			iter = iter.next;
		}
		return false;
	}
	
	// Walk the queue from tail to head, printing values
	public void print () {
		LLNode n = tail;
		while (n != null) {
			System.out.println(n.value);
			n = n.next;
		}
	}
	
	// Walk the queue from head to tail, printing values
	public void printReverse () {
		LLNode n = head;
		while (n != null) {
			System.out.println(n.value);
			n = n.prev;
		}
	}
	
	// Test Client
	public static void main (String [] args) {
		Queue<Integer> test = new Queue<Integer>();
		
		test.push(1);
		test.push(2);
		System.out.println(test.pop() + "\n");
		test.push(3);
		test.printReverse();
		System.out.println();
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		
		test.push(5);
		test.push(11);
		test.push(42);
		test.push(-6);
		
		test.print();
		
		System.out.println();
		
		System.out.println(test.pop());
		System.out.println(test.pop());
		
		test.push(106);
		
		System.out.println();
		
		test.print();
		
		System.out.println();
		System.out.println(test.pop());
		System.out.println(test.pop());
		
		System.out.println();
		test.print();
		
		System.out.println(test.pop());
		System.out.println(test.pop());
		
		
	}
	
	// Doubly linked list node
	class LLNode {
		protected T value;
		protected LLNode next;
		protected LLNode prev;
		
		public LLNode (T value, LLNode next) {
			this.value = value;
			this.next = next;
			this.prev = null;
		}
	}
}
